/**
 * 45. 跳跃游戏 II
 * https://leetcode-cn.com/problems/jump-game-ii/
 */
public class Solutions_45 {
    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 1, 4};  // output: 2
//        int[] nums = {1, 1, 1, 0};  // output: 3
        int result = jump(nums);
        System.out.println(result);
    }

    /**
     * 解法二：动态规划（2ms）
     */
    public static int jump(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        // 第一个位置，跳跃次数为 0
        dp[0] = 0;
        // 从第一个位置，开始跳跃
        int last = 0;
        for (int i = 1; i < len; i++) {
            // 关键：判断 last 位置，能否跳跃到索引 i 上
            while (i > nums[last] + last) {
                // 如果索引 last + 索引上的元素，即能够在 last 索引上，跳跃的最远距离
                // 小于索引 i 时，说明无法跳跃到索引 i 上
                // 那么，last 索引后移，直到 last + nums[last] 最小能够跳跃到索引 i 上
                last++;
            }
            // last 索引上，需要跳跃的次数，加 1，跳跃到索引 i 上
            dp[i] = dp[last] + 1;
        }
        // 最后一个位置时，需要跳跃的次数
        return dp[len - 1];
    }

    /**
     * 解法一：贪心法（3ms）
     */
    public static int jump2(int[] nums) {
        int len = nums.length;
        int res = 0;
        int end = 0, maxPosition = 0;
        // 题目说明：假设你总是可以到达数组的最后一个位置。
        // 所以不用遍历到最后一个元素
        for (int i = 0; i < len - 1; i++) {
            // 比较得到，能够跳跃到的最大索引
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (maxPosition >= len - 1) {
                // 已经计算得到，可以直接跳跃到最后一个位置上
                return ++res;
            }
            // 关键：本次跳跃已经到达了结束位置，那么需要重新跳跃
            if (i == end) {
                // 本次，最远可以跳跃到索引 maxPosition 上
                end = maxPosition;
                res ++;
            }
        }
        return res;
    }
}
